972. Sorting time

Sort the time according to the specified criteria.

Input. The first line contains the number n (1 ≤ n ≤ 100). Then n times are given. Each time is given as three integers – hours (0 to 23), minutes (0 to 60) and seconds (from 0 to 60).

Output. Print the times, sorted in nondecreasing order (time is also displayed in the form of three numbers, do not print the leading zeros).

Sample input	Sample output
4 10 20 30 7 30 00 23 59 59 13 30 30	7 30 0 10 20 30 13 30 30 23 59 59

SOLUTION

sort

Algorithm analysis

Sort the times given in nondecreasing order.

Algorithm realization

Declare the time structure that contains hours, minutes, and seconds.

struct MyTime

{

int hour, min, sec;

};

MyTime lst[100];

The function f is a comparator that sorts the times.

int f(MyTime a, MyTime b)

{

If the hours and the minutes are equal, sort the times in increasing order of seconds.

if ((a.hour == b.hour) && (a.min == b.min)) return a.sec < b.sec;

If the hours are equal but the minutes are not, sort the times in increasing order of minutes.

if (a.hour == b.hour) return a.min < b.min;

Otherwise, sort the times in increasing order of hours.

return a.hour < b.hour;

}

The main part of the problem. Read the input data.

scanf("%d",&n);

for(i = 0; i < n; i++)

scanf("%d %d %d",&lst[i].hour,&lst[i].min,&lst[i].sec);

Sort the time.

sort(lst,lst+n,f);

Print the times.

for(i = 0; i < n; i++)

printf("%d %d %d\n",lst[i].hour,lst[i].min,lst[i].sec);

Algorithm realization – dynamic memory allocation

#include <cstdio>

#include <algorithm>

using namespace std;

int i, n, h, m, s;

struct MyTtime

{

int hour, min, sec;

MyTtime (int hour = 0, int min = 0, int sec = 0) :

hour (hour), min(min), sec(sec) {};

} *lst;

int f(MyTtime a, MyTtime b)

{

if ((a.hour == b.hour) && (a.min == b.min)) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

int main(void)

{

scanf("%d",&n);

lst = new MyTtime[n];

for(i = 0; i < n; i++)

scanf("%d %d %d",&lst[i].hour,&lst[i].min,&lst[i].sec);

sort(lst,lst+n,f);

for(i = 0; i < n; i++)

printf("%d %d %d\n",lst[i].hour,lst[i].min,lst[i].sec);

delete[] lst;

return 0;

}

Algorithm realization – vector

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

int i, n, h, m, s;

struct MyTime

{

int hour, min, sec;

};

vector<MyTime> lst;

int f(MyTime a, MyTime b)

{

if ((a.hour == b.hour) && (a.min == b.min)) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

int main(void)

{

scanf("%d",&n);

lst.resize(n);

for(i = 0; i < n; i++)

scanf("%d %d %d",&lst[i].hour,&lst[i].min,&lst[i].sec);

sort(lst.begin(),lst.end(),f);

for(i = 0; i < n; i++)

printf("%d %d %d\n",lst[i].hour,lst[i].min,lst[i].sec);

return 0;

}

Algorithm realization – implemented comparator

#include <cstdio>

#include <algorithm>

using namespace std;

int i, n, h, m, s;

struct MyTtime

{

int hour, min, sec;

MyTtime (int hour = 0, int min = 0, int sec = 0) :

hour (hour), min(min), sec(sec) {};

int operator< (const MyTtime &a) const

{

if ((hour == a.hour) && (min == a.min)) return sec < a.sec;

if (hour == a.hour) return min < a.min;

return hour < a.hour;

}

} *lst;

int main(void)

{

scanf("%d",&n);

lst = new MyTtime[n];

for(i = 0; i < n; i++)

scanf("%d %d %d",&lst[i].hour,&lst[i].min,&lst[i].sec);

sort(lst,lst+n);

for(i = 0; i < n; i++)

printf("%d %d %d\n",lst[i].hour,lst[i].min,lst[i].sec);

delete[] lst;

return 0;

}

Algorithm realization – swap sort

Declare the time structure that contains hours, minutes and seconds.

struct MyTime

{

int hour, min, sec;

};

Declare the array of structures.

struct MyTime lst[100];

Function f returns 1 if a < b.

int f(MyTime a, MyTime b)

{

If hours and minutes are equal, sort the time in increasing order of seconds.

if ((a.hour == b.hour) && (a.min == b.min)) return a.sec < b.sec;

If hours are equal (minutes are not equal), sort the time in increasing order of minutes.

if (a.hour == b.hour) return a.min < b.min;

Otherwise sort the time in increasing order of hours.

return a.hour < b.hour;

}

Function swap swaps the times a and b.

void swap(MyTime &a, MyTime &b)

{

MyTime temp = a; a = b; b = temp;

}

The main part of the problem. Read the input data.

scanf("%d", &n);

for (i = 0; i < n; i++)

scanf("%d %d %d", &lst[i].hour, &lst[i].min, &lst[i].sec);

Sort the data using a swap sort.

for (i = 0; i < n; i++)

for (j = i + 1; j < n; j++)

if (!f(lst[i], lst[j])) swap(lst[i], lst[j]);

Print the sorted data.

for (i = 0; i < n; i++)

printf("%d %d %d\n", lst[i].hour, lst[i].min, lst[i].sec);

Algorithm realization – Heap Sort

#include <stdio.h>

#define MAX 1001

int i, n;

struct MyTime

{

int hour, min, sec;

MyTime() {};

MyTime(MyTime &a) : hour(a.hour), min(a.min), sec(a.sec) {};

};

MyTime lst[MAX];

int f(MyTime a, MyTime b)

{

if ((a.hour == b.hour) && (a.min == b.min)) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

int left(int i)

{

return 2 * i;

}

int right(int i)

{

return 2 * i + 1;

}

void swap(MyTime &i, MyTime &j)

{

MyTime temp = i; i = j; j = temp;

}

// max - heap

void heapify(MyTime a[], int i, int n)

{

int largest = 0;

int l = left(i);

int r = right(i);

if (l <= n && f(a[i], a[l])) largest = l;

else largest = i;

if (r <= n && f(a[largest], a[r])) largest = r;

if (largest != i)

{

swap(a[i], a[largest]);

heapify(a, largest, n);

}

}

void BuildHeap(MyTime a[], int n)

{

for (int i = n / 2; i > 0; i--)

heapify(a, i, n);

}

void HeapSort(MyTime a[], int n)

{

BuildHeap(a, n);

for (int i = n; i >= 2; i--)

{

swap(a[1], a[i]);

heapify(a, 1, i - 1);

}

}

int main(void)

{

scanf("%d", &n);

for (i = 1; i <= n; i++)

scanf("%d %d %d", &lst[i].hour, &lst[i].min, &lst[i].sec);

HeapSort(lst, n);

for (i = 1; i <= n; i++)

printf("%d %d %d\n", lst[i].hour, lst[i].min, lst[i].sec);

printf("\n");

return 0;

}

Algorithm realization – MergeSort

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

int i, n, h, m, s;

struct MyTime

{

int hour, min, sec;

MyTime() {};

MyTime(int hour, int min, int sec) :

hour(hour), min(min), sec(sec) {};

};

MyTime lst[100];

int f(MyTime a, MyTime b)

{

if ((a.hour == b.hour) && (a.min == b.min)) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

void merge(MyTime a[], int bleft, int bright, int cleft, int cright)

{

// a[bleft..bright] and a[cleft..cright] are merged into a[bleft..cright]

int i, left = bleft, len = cright - bleft + 1;

MyTime *res = new MyTime[len];

for (i = 0; i < len; i++)

{

if ((bleft > bright) || (cleft > cright)) break;

if (f(a[bleft], a[cleft])) res[i] = a[bleft], bleft++;

else res[i] = a[cleft], cleft++;

}

while (bleft <= bright) res[i++] = a[bleft++];

while (cleft <= cright) res[i++] = a[cleft++];

for (i = left; i < left + len; i++) a[i] = res[i - left];

delete[] res;

}

void mergeSort(MyTime a[], int left, int right)

{

if (left >= right) return;

int middle = (left + right) / 2;

mergeSort(a, left, middle);

mergeSort(a, middle + 1, right);

merge(a, left, middle, middle + 1, right);

}

int main(void)

{

scanf("%d", &n);

for (i = 1; i <= n; i++)

scanf("%d %d %d", &lst[i].hour, &lst[i].min, &lst[i].sec);

mergeSort(lst, 1, n);

for (i = 1; i <= n; i++)

printf("%d %d %d\n", lst[i].hour, lst[i].min, lst[i].sec);

return 0;

}

Algorithm realization – QuickSort

#include <cstdio>

#include <vector>

using namespace std;

int i, n, h, m, s;

struct MyTime

{

int hour, min, sec;

};

vector<MyTime> lst;

int f(MyTime a, MyTime b)

{

if ((a.hour == b.hour) && (a.min == b.min)) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

void swap(int &i, int &j)

{

int temp = i; i = j; j = temp;

}

int Partition(vector<MyTime> &m, int L, int R)

{

MyTime x = m[L];

int i = L - 1, j = R + 1;

while (1)

{

do j--; while (f(x, m[j]));

do i++; while (f(m[i], x));

if (i < j) swap(m[i], m[j]); else return j;

}

}

void QuickSort(vector<MyTime> &m, int L, int R)

{

int q;

if (L < R)

{

q = Partition(m, L, R);

QuickSort(m, L, q); QuickSort(m, q + 1, R);

}

}

int main(void)

{

scanf("%d", &n);

lst.resize(n);

for (i = 0; i < n; i++)

scanf("%d %d %d", &lst[i].hour, &lst[i].min, &lst[i].sec);

QuickSort(lst, 0, lst.size() - 1);

for (i = 0; i < n; i++)

printf("%d %d %d\n", lst[i].hour, lst[i].min, lst[i].sec);

return 0;

}

Java realization

import java.util.*;

class MyTime

{

int hour;

int min;

int sec;

public MyTime(int hour, int min, int sec)

{

this.hour = hour;

this.min = min;

this.sec = sec;

}

}

public class Main

{

public static class MyFun implements Comparator<MyTime>

{

public int compare(MyTime a, MyTime b)

{

if (a.hour == b.hour && a.min == b.min) return a.sec - b.sec;

if (a.hour == b.hour) return a.min - b.min;

return a.hour - b.hour;

}

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

ArrayList<MyTime> tm = new ArrayList<MyTime>();

for (int i = 0; i < n; i++)

tm.add(new MyTime(con.nextInt(), con.nextInt(), con.nextInt()));

Collections.sort(tm, new MyFun());

for (int i = 0; i < n; i++)

System.out.println(tm.get(i).hour + " " + tm.get(i).min + " " + tm.get(i).sec);

con.close();

}

}

Java realization – Heap sort

import java.util.*;

class MyTime

{

int hour;

int min;

int sec;

public MyTime(int hour, int min, int sec)

{

this.hour = hour;

this.min = min;

this.sec = sec;

}

}

public class Main

{

public static boolean f(MyTime a, MyTime b)

{

if (a.hour == b.hour && a.min == b.min) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

static int left(int i)

{

return 2 * i;

}

static int right(int i)

{

return 2 * i + 1;

}

static void swap(MyTime a[], int i, int j)

{

MyTime temp = a[i]; a[i] = a[j]; a[j] = temp;

}

//max - heap

static void heapify(MyTime a[], int i, int n) // n = size of a heap

{

int largest = 0;

int l = left(i);

int r = right(i);

if (l <= n && f(a[i],a[l])) largest = l;

else largest = i;

if (r <= n && f(a[largest],a[r])) largest = r;

if (largest != i)

{

swap(a, i, largest);

heapify(a, largest, n);

}

}

static void BuildHeap(MyTime a[], int n)

{

for (int i = n / 2; i > 0; i--)

heapify(a, i, n);

}

static void HeapSort(MyTime a[], int n)

{

BuildHeap(a, n);

for (int i = n; i >= 2; i--)

{

swap(a, 1, i);

heapify(a, 1, i - 1);

}

}

public static void main(String[] args) {

Scanner con = new Scanner(System.in);

int n = con.nextInt();

MyTime[] tm = new MyTime[n+1];

for (int i = 1; i <= n; i++)

tm[i] = new MyTime(con.nextInt(), con.nextInt(), con.nextInt());

HeapSort(tm, n);

for (int i = 1; i <= n; i++)

System.out.println(tm[i].hour + " " + tm[i].min + " " + tm[i].sec);

System.out.println();

con.close();

}

}

Java realization – MergeSort

import java.util.*;

class MyTime

{

int hour;

int min;

int sec;

public MyTime(int hour, int min, int sec)

{

this.hour = hour;

this.min = min;

this.sec = sec;

}

}

public class Main

{

public static boolean f(MyTime a, MyTime b)

{

if (a.hour == b.hour && a.min == b.min) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

static void merge(MyTime a[], int bleft, int bright, int cleft, int cright)

{

// a[bleft..bright] and a[cleft..cright] are merged

// into a[bleft..cright]

int i, left = bleft, len = cright - bleft + 1;

MyTime res[] = new MyTime[len];

for (i = 0; i < len; i++)

{

if ((bleft > bright) || (cleft > cright)) break;

if (f(a[bleft],a[cleft]))

{

res[i] = a[bleft];

bleft++;

}

else

{

res[i] = a[cleft];

cleft++;

}

}

while (bleft <= bright) res[i++] = a[bleft++];

while (cleft <= cright) res[i++] = a[cleft++];

for (i = left; i < left + len; i++) a[i] = res[i - left];

}

static void mergeSort(MyTime a[], int left, int right)

{

if (left >= right) return;

int middle = (left + right) / 2;

mergeSort(a, left, middle);

mergeSort(a, middle + 1, right);

merge(a, left, middle, middle + 1, right);

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

MyTime[] tm = new MyTime[n+1];

for (int i = 1; i <= n; i++)

tm[i] = new MyTime(con.nextInt(), con.nextInt(), con.nextInt());

mergeSort(tm, 1, n);

for (int i = 1; i <= n; i++)

System.out.println(tm[i].hour + " " + tm[i].min + " " + tm[i].sec);

System.out.println();

con.close();

}

}

Java realization – QuickSort

import java.util.*;

class MyTime

{

int hour;

int min;

int sec;

public MyTime(int hour, int min, int sec)

{

this.hour = hour;

this.min = min;

this.sec = sec;

}

}

public class Main

{

public static boolean f(MyTime a, MyTime b)

{

if (a.hour == b.hour && a.min == b.min) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

static void swap(MyTime a[], int i, int j)

{

MyTime temp = a[i]; a[i] = a[j]; a[j] = temp;

}

static int Partition(MyTime a[], int L, int R)

{

MyTime x = a[L];

int i = L - 1, j = R + 1;

while (true)

{

do j--; while (f(x,a[j]));

do i++; while (f(a[i],x));

if (i < j) swap(a, i, j); else return j;

}

}

static void QuickSort(MyTime a[], int L, int R)

{

if (L < R)

{

int q = Partition(a, L, R);

QuickSort(a, L, q);

QuickSort(a, q + 1, R);

}

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

MyTime[] tm = new MyTime[n+1];

for (int i = 1; i <= n; i++)

tm[i] = new MyTime(con.nextInt(), con.nextInt(), con.nextInt());

QuickSort(tm, 1, n);

for (int i = 1; i <= n; i++)

System.out.println(tm[i].hour + " " + tm[i].min + " " + tm[i].sec);

System.out.println();

con.close();

}

}